#include "dynamicarray.h"

struct dynamicarray
{
    // 数组指针
    ElementType *array;
    // 数组的容量
    int capacity;
    // 元素的个数
    int size;
};

DArray *InitDArray()
{
    DArray *a = (DArray *)malloc(sizeof(DArray));
    if (a == NULL)
    {
        printf("InitDArray malloc error!\n");
        // 退出程序
        exit(-1);
    }

    a->size = 0;
    a->capacity = 10;
    a->array = (ElementType *)malloc(sizeof(ElementType) * a->capacity);
    if (a->array == NULL)
    {
        printf("InitDArray array malloc error!\n");
        exit(-1);
    }

    return a;
}

void InsertDArray(DArray *a, ElementType element)
{
    if (a->size == a->capacity)
    {
        a->capacity *= 2;
        a->array = (ElementType *)realloc(a->array, a->capacity * sizeof(ElementType));
        if (a->array == NULL)
        {
            printf("InsertDArray realloc error!\n");
            exit(-1);
        }
    }
    a->array[a->size] = element;
    (a->size)++;
}

void PrintDArray(DArray *a, void (*print)(ElementType))
{
    printf("capacity: %d size %d\n", a->capacity, a->size);
    for (int i = 0; i < a->size; i++)
    {
        print(a->array[i]);
    }
    printf("\n");
}

ElementType FindByElement(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for (int i = 0; i < a->size; i++)
    {
        if (compare(a->array[i], value))
        {
            return a->array[i];
        }
    }
    return NULL;
}

ElementType RemoveByIndex(DArray *a, int index)
{
    ElementType result = a->array[index];
    for (int i = 0; i < a->size - 1; i++)
    {
        a->array[i] = a->array[i + 1];
    }
    a->size--;
    return result;
}

ElementType RemoveDArray(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{

    for (int i = 0; i < a->size; i++)
    {
        if (compare(a->array[i], value))
        {
            return RemoveByIndex(a, i);
        }
    }
    return NULL;
}

void MyFastSort(ElementType *a, int start, int end, bool (*compare)(ElementType, ElementType))
{
    // 终止条件
    if (start >= end)
    {
        return;
    }

    int left = start;
    int right = end;

    ElementType temp = a[start];
    while (left < right)
    {
        // 从右往左找比基准值小的
        while (compare(a[right], temp) && left < right)
        {
            right--;
        }
        if (left < right)
        {
            // 把比基准值小的数放在左边
            a[left] = a[right];
            left++;
        }
        // 从左往右找比基准值大的
        while (compare(temp, a[right]) && left < right)
        {
            left++;
        }

        if (left < right)
        {
            // 把比基准值大的放右边
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;

    MyFastSort(a, start, left - 1, compare);
    MyFastSort(a, right + 1, end, compare);
}

ElementType BinarySearch(DArray *a, ElementType value, int (*compare)(ElementType, ElementType))
{
    int left = 0;
    int right = a->size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        // int mid=(left & right)+((left^right)>>1);
        if (compare(a->array[mid],value)==0)
        {
            return a->array[mid];
        }
        else if (compare(a->array[mid],value)>0)
        {
            right = mid - 1;
        }
        else if (compare(a->array[mid],value)<0)
        {
            left = mid + 1;
        }
    }

    return NULL;
}

void FastSort(DArray *a, bool (*compare)(ElementType, ElementType))
{
    MyFastSort(a->array, 0, a->size - 1, compare);
}

// void DeleteElement(DArray *a, ElementType value, bool (*compare)(ElementType,ElementType))
// {
//     for (int i = 0; i < a->size; i++)
//     {
//         if (compare(a->array[i],value))
//         {
//             a->array[i]=a->array[i+1];
//         }
//     }
//     a->size--;
//     printf("delete!\n");
// }

void ClearDArray(DArray *a, void (*clear)(ElementType))
{
    if (a != NULL)
    {
        for (int i = 0; i < a->size; i++)
        {
            clear(a->array[i]);
        }
        free(a->array);
        free(a);
    }
}
